from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 创建DP数组，dp[i]表示凑成金额i所需的最少硬币数
        # 初始化为无穷大，表示暂时无法凑成
        dp = [float('inf')] * (amount + 1)

        # 基础情况：金额为0时不需要任何硬币
        dp[0] = 0

        # 遍历所有金额，从1到amount
        for i in range(1, amount + 1):
            # 遍历所有硬币面额
            for coin in coins:
                # 如果当前硬币面额小于等于目标金额
                if coin <= i:
                    # 状态转移：选择当前硬币，数量+1，取最小值
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        # 如果dp[amount]仍然是无穷大，说明无法凑成，返回-1
        # 否则返回最少硬币数量
        return dp[amount] if dp[amount] != float('inf') else -1